This invention relates to cryptographic systems comprised of at least one encryption station, at least one decryption station and a trapdoor generator.
Cryptographic systems of this kind are useful as public key cryptographic systems provided with a trapdoor one-way function allowing message encryption and decryption, digital signature schemes and user identification protocols.
Generally, cryptographic systems are widely used to ensure the privacy and authenticity of messages transmitted over public communication channels, such as telephone lines, which are considered to be insecure communication channels. Cryptographic systems are heavily relied on in military, diplomatic and business communications for the transfer of information, including voice, picture and text data, and for identification purposes.
One type of cryptographic system, generally known as a privacy system, prevents extraction of information by unauthorized parties from messages transmitted over an insecure communication channel, thus assuring a sender that a message being sent is read only by an intended receiver. Another type of cryptographic system, generally known as a digital signature scheme, allows the sender of a message to code this message into a signature in such a way that nobody else can generate the signature corresponding to a given message, but everybody can easily verify the signature claimed to correspond to a given message. Yet another type of cryptographic system, generally known as an identification protocol, allows a person (or computer) to prove its identity to a challenger without revealing any information (e.g., a password) that would later allow the verifier to impersonate himself as the previously examined person (or computer).
A conventional type of cryptographic privacy system allows a sender to transmit a plaintext message M to a receiver over an insecure communication channels, e.g. a telephone line. At the sender's site, an encryption device encodes the plaintext message M with the help of a secret key into a ciphertext message C which is then transmitted. At the receiver's site, a decryption device decodes the ciphertext message C back into the plaintext message M with the help of the secret key. Given the knowledge of this secret key, the pertaining encryption and decryption transformations can be performed on the message, absent this knowledge they cannot be performed even with the most powerful computers known or conceivable at present times. Thus, for an eavesdropper who wants to decipher the message and yet is assumed to have no information about the secret key it is not feasible to determine the plaintext message M corresponding to a given ciphertext C, nor is it feasible to determine the secret key when given matching plaintext and ciphertext pairs. However, one problem with this system is that it requires the distribution of secret keys to the communicating parties. This is often done over a secure channel such as priority mail, or in advance using a trusted courier, which can be expensive or even impossible, as in many military applications.
A conventional non-cryptographic signature system is set up as follows. A person wishing to sign documents (e.g. a cheque) deposits an original version of his/her signature at the institution (e.g. a bank) that is supposed to later verify the issued signatures. The original signature could also be made publicly available in a signature directory if everybody should be enabled to verify the signature. The authenticity of documents claimed to be issued by a certain person can be checked, for instance by a judge, by comparing the signature on the document with the original signature. The security of conventional signatures relies in a crucial way on the following assumptions, the importance of all of which is often not completely realized by users of signatures: (1) a person is always able to produce a signature that is sufficiently similar to his/her original signature (capability to reproduce), (2) nobody else is capable of producing signatures that are sufficiently similar to the original signature (impossibility to forge), (3) it is impossible to transfer a valid signature from one document to another (impossibility to transfer), and (4) it is easy for anyone wishing to verify a signature to judge the degree of similarity of a signature with the original (capability to verify).
A conventional non-cryptographic identification protocol can be set up essentially in two different ways. The first way is to let a trusted authority issue a document (e.g. a passport) to every person who applies for a means of being identified. The security of such a system relies on the assumptions that (1) passports cannot be forged and (2) given a passport and a person, it is easy to verify whether they match or not. The second way is to let each person choose a password that is then registered in a password file. This second approach is often used for computer applications where it is impossible to verify certain identification criteria (e.g. eye color), however, it has a crucial security problem: anyone who knows the password, for instance the computer to which a person has identified his/herself, can later impersonate as this person.
Messages exchanged in computer-based cryptographic systems are represented digitally, i.e. they are made up of sequences of numbers and/or letters. Therefore, it should seem inherently impossible to build a cryptographic digital signature system, since every signature would be a digital number that can trivially be copied and hence forged. Similarly, it should seem that no cryptographic identification protocol of the first kind discussed above could exist that prevents a verifier, after he has seen a digital number that convinces him of the identity of a person, from later reusing the same number to impersonate as the previously identified person.
Reference will be made hereinafter to a "user" or "party" rather than to a "person" so as to indicate that in many applications, it is computer systems rather than persons that are communicating and the "user" or "party" then is a device.
A major breakthrough in cryptography was achieved in 1976 when W. Diffie and M. E. Hellman published their seminal paper "New directions in cryptography" in IEEE Trans. on Inform. Theory, vol. IT-22, pp. 664-654, Nov. 1976 (cf. also patent US-A-4200770). Diffie and Hellman proposed a protocol by which two parties A and B who initially do not share any secret whatsoever can talk over a completely insecure channel (e.g. a telephone line that can be tapped by an eavesdropper), and at the end of the protocol each party comes up with one and the same secret key which it is for the eavesdropper completely infeasible to determine, even when given all messages exchanged between A and B. Moreover, Diffie and Hellman suggested that digital signature schemes could be set up if there could be devised a certain type of transformation based on a so-called trapdoor one-way function. However, Diffie and Hellman did not propose an implementation of a trapdoor one-way function, nor did they prove that such a function exists.
Loosely speaking, a trapdoor one-way function is a transformation that maps the elements of a domain set {D} to the elements of a range set {R} such that
(1) the transformation is invertible, i.e., every element in the range set corresponds to exactly one element in the domain set,
(2) given an element of the domain set, it is easy to compute the corresponding transformed element in the range set, and
(3) given an element in the range set, it is completely infeasible to compute the corresponding element in the domain set unless one knows a secret piece of information (the trapdoor).
Diffie and Hellman suggested that a trapdoor one-way function could be used in two different ways. In both applications, a user publishes a description of a trapdoor one-way function while keeping the trapdoor secret. Any other user can thus compute the forward transformation, but none except the legitimate user can feasibly compute the inverse transformation. Here and hereinafter, the solution of a problem is deemed infeasible if no computer system known or conceivably available in a foreseeable future can solve the problem in a reasonable time (e.g. in less than 100 years).
The first of the two applications suggested by Diffie and Hellman is called a public-key cryptographic system. A user can publicly announce an encryption transformation for plaintext messages of such kind that only this user has the capability of deciphering received ciphertext messages. This is achieved by using the trapdoor one-way function as the encryption transformation and its inverse as the corresponding decryption operation. Clearly, all users must agree on a common way of representing plaintext messages as elements of the domain set {D} and ciphertext messages as elements of the range set {R}.
The second application suggested by Diffie and Hellman is called a digital signature scheme. A user can publicly disclose (e.g. register in a public directory similar to the deposition of an original signature) a signature verification transformation such that only this user has the capability of generating the signature corresponding to a given message to be signed. This is achieved by using the trapdoor one-way function as the signature verification transformation and its inverse as the corresponding signature generation transformation. Clearly, all users must agree on a common way of representing messages as elements of the range set {R} and signatures as elements of the domain set {D}. Such a digital signature scheme satisfies the four criteria for signature schemes mentioned above. In particular, transferring signatures is prevented by the fact that each signature only signs one particular message. The fact that one can easily reproduce an issued signature does not harm the system because the signed message cannot be modified. The problem that someone can produce a signature at random without knowing which message it signs can be solved by requiring that the messages be of a special form, e.g. redundant.
It may be noted that the trapdoor one-way function and its inverse are applied in respectively opposite order when a digital signature scheme and a public-key cryptographic system are performed.
The first practical implementation of a trapdoor one-way function and thus, of a public key cryptographic system and a digital signature scheme based on Diffie and Hellman's idea, is described in patent U.S. Pat. No. 4405829 to Rivest, Shamir and Adleman (cf. also R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM, vol. 21, pp. 120-126, 1978. According to this teaching, a user establishes a so-called RSA trapdoor one-way function by generating two large prime numbers p and q (e.g. each having 100 decimal digits) and selecting a number e that is relatively prime to (p-1) and (q-1). Generating large prime numbers is feasible and known in the art (cf. for instance U. M. Maurer, "Fast generation of secure RSA-moduli with almost maximal diversity", Advances in Cryptology--Eurocrypt'89, Lecture Notes in Computer Science, Vol. 434, Springer Verlag, Berlin, 1990, pp. 636-647, or M. O. Rabin, "Probabilistic algorithms for testing primalty", J. of Number Theory, vol. 12, pp. 128-138, 1980). The user then publishes the product m=p.multidot.q of the two primes as well as the exponent e and computes secretly the unique number d satisfying the conditions EQU 0.ltoreq.d.ltoreq.1 cm[(p-1), (q-1)]
and EQU d.multidot.e.ident.1 (mod 1 cm[(p-1), (q-1)])
where 1 cm denotes the least common multiple of the numbers listed in the brackets and mod denotes the modulo function, the following features of which are of particular interest hereinafter:
The meaning of congruence equation a.ident.b (mod c) is that and b have the same remainder when divided by c, which is equivalent to the statement that (a-b) is a (possibly negative or zero) multiple of c. Hereinafter, unless specified differently, b can be any expression involving several numbers or variables, and a is equal to the smallest non-negative integer number that satisfies the above congruence equation a.ident.b (mod c). For instance, the above two congruence equations EQU 0.ltoreq.d.ltoreq.1 cm(p-1) (q-1)
and EQU d.multidot.e.ident.1 (mod 1 cm[(p-1).multidot.(q-1)])
can be replaced by the single equivalent equation EQU d.ident.1/e (mod (p-1).multidot.(q-1)).
In the above mentioned teaching of Rivest, Shamir and Adleman, d is the secret trapdoor of the RSA trapdoor one-way function. Finding d is generally believed infeasible since it requires knowledge of the prime factors of the modulus m and it is generally believed that factoring large integers into their prime factors is a problem infeasible by computation.
The basic operation required to implement the RSA trapdoor one-way function as well as its inverse is exponentiation modulo the given number m, which will be called the modulus, while e and d will be referred to as the public and the secret exponent, respectively.
There exist well-known techniques for implementing modular arithmetic (cf. for instance D. E. Knuth, "The art of computer programming", vol. 2, 2nd edition, Reading, Mass.: Addison-Wesley, 1981). In particular, a modular exponentiation technique called "square and multiply" is known that is very fast, even when the exponent is a number having several 100 decimal digits. The domain set and the range set of the RSA trapdoor one-way function both are equal to the set Z.sub.m of non-negative integers smaller than m, i.e. {D}={R}=Z.sub.m ={0,1, . . . , (m-1)}.
To compute the trapdoor one-way function transformation for a given argument x .epsilon. Z.sub.m resulting in the transformed value y, the argument x is raised to the e-th power modulo m, i.e. y.ident.x.sup.e (mod m). The inverse transformation, viz. raising y to the d-th power modulo m, is similar but can only be performed when the trapdoor d is known, and results in x as has been proved in the above-quoted publication by Rivest, Shamir and Adleman, i.e. x.ident.y.sup.d (mod m).
Another application of the RSA trapdoor one-way function was proposed by Fiat and Shamir in U.S. Pat. No. 4748668 (cf. also A. Fiat and A. Shamir, "How to prove yourself: practical solutions to identification and signature problems", Proceeding of CRYPTO '86, Lecture Notes in Computer Science, Vol. 263, Springer Verlag, Berlin, 1987, pp. 186-194). A simplified version of their identification protocol is discussed in the following. A user receives from a trusted authority the secret number s such that s.sup.2 .ident.ID (mod m), where ID is a number representing an identity information for identification of the user and m is the product of two large prime numbers. It may be noted that s is the square root modulo m of the number ID. It has been shown that in order to be able to compute square roots modulo m one must know the prime factors of m, which are kept secret by the trusted authority. In order to prove itself, rather than to reveal s and allow the challenger to verify that s.sup.2 .ident.ID (mod m) (and thereafter to enable the challenger to impersonate as the user), the user only proves that he knows s, but without revealing it. In fact, one can prove that even if the identification protocol is repeated several times, a challenger cannot obtain any information about s whatsoever that he did not possess before execution of the protocol.
In a simplified version, the Fiat-Shamir protocol works as follows. The user chooses a random number r in Z.sub.m that is relatively prime to m and sends to the challenger the number r.sup.2 (mod m) together with the claimed identity information ID. The challenger challenges the user by issuing a randomly chosen binary number b. If b=0, the user must reply by sending r so as to prove that the previously sent r.sup.2 was indeed a number of which it knew the square root. If b=1, the user must reply with the number r.multidot.s (mod m) so as to prove that it knows both r and s. Since the user can each time cheat in this protocol with a 50% chance only, namely when it guesses the challenge variable b correctly in advance, the challenger can be convinced that the user knows s if the protocol is run several times consecutively. The probability of guessing correctly a sequence of n random bits is 2.sup.-n, which is a very small number when n is sufficiently large.
One way of breaking the RSA trapdoor one-way function is by computing the trapdoor exponent d. It has been proved that it is no easier to determine d than it is to find the prime factors p and q of the public modulus m, which, as mentioned above, is assumed to be a very difficult problem. However, it has not been proved that in order to break the cryptographic system based on the RSA trapdoor one-way function it is necessary to compute d and thus to factor m.